Moving a solid object from one location to another location without bumping or penetrating fixed obstacles on its way is a classical problem that has many applications in many fields. This problem is commonly called the motion planning problem (also called the path planning or the piano movers problem). In this problem, the goal is to find an interference-free (also called collision-free or non-overlapping) trajectory for a collection of moving objects amidst fixed obstacles from an initial to final configuration. An instance of the motion planning problem that is relevant here is the so-called "peg-in-hole" problem, in which a moving peg (the body) is to be inserted without interferences into a fixed hole (the fixed obstacle). Typically, the peg and the hole are tightly fit, so that the clearance between the peg and the hole is small and the peg and hole shapes are almost complementary. This requires fine motions to insert the peg into the hole. The interference-free insertion problem is related to the design and modifications of the peg and hole shapes such that the peg will not get stuck during its insertion inside the hole. A fundamental reference that formulates and describes solutions for this class of problems is Robot Motion Planning by Jean-Claude Latombe published by Kluwer Academic Publishers dated 1991, which is herein incorporated by reference in its entirety.
Solutions to the peg-in-hole problem have many applications in molding, manufacturing, assembly, medicine, and robotics, among others, in which a solid body is to be inserted or removed along a complex interference-free trajectory into a cavity. The analysis and solution of the interference-free insertion problem is used for designing tighter fits (force fits) for machine parts, for designing easily assemblable machines, for designing removable molds in part manufacturing, and for designing medical implants, among others.
There are basically two types of motion planning problems (including peg-in-hole): 1. those where the trajectory from the initial to the final configuration is known and 2. those where the trajectory is unknown and must be determined. In the first type of problem, the solid body trajectory from the initial to the final configuration has been determined beforehand; all is left is to verify that the trajectory is interference-free. This is done by testing for interferences between the moving body and the fixed obstacles at successive configurations along the trajectory. This solution is applicable to problems in which the trajectory is simple and can be easily determined from the shapes of the bodies. It is inapplicable for inserting a tightly fit body into a cavity because tight fit insertion requires many small incremental motions that can only be determined quantitatively from the body and cavity shapes.
The second type of problem, where the trajectory from the initial to the final configuration is unknown, covers the majority of motion planning problems, and in particular the interference-free insertion of a tightly fit body into a cavity. Some prior art finds an interference-free trajectory by searching the space of non-interference object configurations (the configuration space) for a continuous trajectory from the initial to the final configuration. The prior art discloses two strategies for searching this space--global strategies and local strategies. Global strategies first construct the configuration space and its connectivity graph and then search it for the desired trajectory. Local strategies directly search for the trajectory, performing geometric computations as the search progresses.
Global methods require computing the configuration space, whose complexity is polynomial in the geometric size of the objects and exponential in their total number of degrees of freedom. When the body and the cavity have tightly fit complex 3-dimensional shapes, the insertion trajectory requires thousands of small, incremental, coupled 6 degree of freedom motions (three translations and three rotations) to take the body from the starting to the final configuration. This makes global strategies and their variations (such as hierarchical configuration space decomposition, planning in low-dimensional configuration space projections, and exploiting the solid body geometrical regularities) impractical or inadequate. The configuration space corresponding to this problem is very large and complex, making its construction and search impractical.
Local strategies depend on the efficiency of the geometric computations and the effectiveness of the search strategy. Existing local strategies emphasize search effectiveness. Some prior art algorithms for a moving six degree of freedom polyhedron place a fine resolution grid on the configuration space and uses a set of heuristics based on the local configuration space geometry to search for the trajectory. For a tight fit, this method requires a very fine grid resolution and precise geometric computations which significantly affect the overall efficiency. Because of the fine grid resolution, very many small incremental motions from one grid point to the other are required to construct a trajectory from the initial to the final configuration. Other local strategies, such as the so-called potential field method or any strategy that repeatedly tests for object interferences as the trajectory is constructed are impractical as well. Because of the shape complexity, the interference tests are expensive. Further, many such tests are required because the fit between the shapes is tight, forcing the incremental motions towards the final configuration to be very small.
Solutions to the motion planning problem have applications in the medical arts, particularly in the design and manufacture of implants and the determination of implant insertion/removal trajectories. Computer-based medical imaging and modeling systems, coupled with computer-aided design and manufacturing technology, have already begun to have a major impact on the clinical practice of medicine. The design and fabrication of custom orthopedic implants from catscan (CT) data is one growing application of such systems. One class of implants, cementless implants, relys on a press fit, or tissue ingrowth, and significant surface-to-surface contact between the implant and the bone for fixation. The accuracy of bone preparation can have a significant effect on implant efficacy for these cementless implants.
Recent advances in robot bone machining have demonstrated an order-of-magnitude improvement in the accuracy of femoral canal preparation for hip replacement surgery. While improved implant design and fabrication and improved accuracy and consistency of bone preparation will greatly improve the surface-to-surface contact between the implant and the bone, i.e., the fixation, these improvements result from reduced tolerances that could restrict the insertion of the implant into the bone. Accordingly, improved methods and apparatuses must be made available to facilitate moving the implant along a correct trajectory so that the implant does not become stuck in the bone prior to reaching its final configuration.
To illustrate, in cementless hip replacement surgery, the damaged joint is replaced by an orthopedic implant which fits tightly into the femur. To install such implants, the surgeon typically starts by sawing off the femoral head and drilling a guide hole down the femur using a flexible reamer. The surgeon then drives a broach into the guide hole to make a cavity with the same shape as the implant. Since the broach shape matches the implant shape and the broach has been inserted into the cavity, there is some assurance that the implant will fit into the cavity carved by the broach. Unfortunately, the broach design may require the removal of bone which, for implant efficiency, would perhaps be better left intact. In summary, manually shaping the femur cavity with a broach allows a tight fit but still leaves undesirably large tolerances between the cavity and implant surfaces.
Robots can be employed to cut these cavity contours in the bone to attain a very tight fit (very small tolerances) between the implant and the cavity when the implant reaches its desired, final configuration in the bone. However, although the robot can machine a cavity with the desired shape within small tolerances, these small tolerances reduce the chance that the implant can actually be inserted into the cavity. It is highly undesirable discover this situation in the operating room. It would be much better to discover an insertability problem after the implant is designed and before it is fabricated. It is ever more desirable to identify a feasible insertion trajectory automatically, if one exists, and to identify possible places for design modification (of the cavity cut and/or implant shape) if such trajectory cannot be found.